contents

💡 코딩 테스트를 위한 비트 연산(Bit Manipulation) 가이드 및 예제

비트 연산은 빠른 계산(O(1)), 공간 절약, 특수 알고리즘/최적화에서 매우 유용하며, 코딩 테스트와 면접에서 자주 출제됩니다.

1. 비트 연산의 기본 개념

• 비트 연산은 정수의 이진수(비트) 단위로 직접 AND, OR, XOR, SHIFT 등을 수행하는 기법입니다.
• 장점: 매우 빠른 연산, 최적화/특수 알고리즘 구현에 필수
• 활용: 홀/짝 판별, 집합, 비트 토글, 유일값 찾기, 부분집합 생성 등

2. 자주 쓰는 비트 연산자

3. 비트 연산 기본 트릭

a. 홀수/짝수 판별

• x % 2 == 0 ↔ (x & 1) == 0
• 홀수는 마지막 비트가 1, 짝수는 0

b. 두 수 스왑(XOR 스왑)

a ^= b;
b ^= a;
a ^= b;

(임시변수 없이 가능)

c. k번째 비트 설정/해제/토글

• 설정(Set): x |= (1 << k)
• 해제(Clear): x &= ~(1 << k)
• 토글(Toggle): x ^= (1 << k)

4. 비트 카운트 및 위치 탐색

a. 설정된 비트 개수 세기(Kernighan 알고리즘)

int countBits(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1);
        count++;
    }
    return count;
}

설정된 비트를 하나씩 제거

b. k번째 비트 추출

int getKthBit(int n, int k) {
    return (n >> k) & 1;
}

c. 가장 낮은 설정 비트 추출

int lowestBit = n & -n;

(최하위 1비트만 남김)

5. 비트마스크(Bitmask)를 이용한 부분집합/상태 표현

• n개 요소의 모든 부분집합 → 0~(1<<n)-1까지 비트마스크로 표현
• 각 비트의 위치가 원소 포함 여부를 의미

부분집합 생성 예시:

for (int mask = 0; mask < (1 << n); mask++) {
    for (int i = 0; i < n; i++) {
        if (((mask >> i) & 1) == 1) {
            // i번째 원소 포함
        }
    }
}

6. 대표 비트 문제

a. 수열에서 한 번만 나타나는 원소 찾기 (Single Number)

int unique = 0;
for (int num : arr)
    unique ^= num;
return unique;

(XOR로 중복 제거, 단일 원소만 남음)

b. 홀수 번 등장 원소 찾기

• 위 XOR 트릭과 동일

c. 2의 거듭제곱 판별

boolean isPowerOf2(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

(1비트만 설정된 수)

d. Sieve(에라토스테네스 등)에 비트마스크 활용

• 배열 대신 정수의 비트를 flag로 사용해 공간 절약

7. 면접/코테에서의 패턴별 활용

8. 고급 비트 트릭

• 비트 반전(reverse), 빠른 popcount
• 비트마스크의 다음 순열(Gosper’s hack)
• Gray 코드 생성
• 최고/최저 1비트 위치 잡기

9. 실수/주의 사항

• 부호가 있는 정수의 시프트·연산 시 주의(특히 음수)
• NOT(~) 연산은 부호 반전, 타입 조심
• 낮은 수준 비트 연산은 unsigned 타입이나 C++/Python 사용시 더 자유로움

10. 요약 표 – 비트 연산 코딩 시험 패턴

💡 비트 연산 코딩 테스트 대표 빈출 문제 & 풀이/트릭 정리

아래는 코딩 테스트와 면접에서 가장 자주 출제되는 비트 연산 문제와 기본 솔루션 및 핵심 아이디어입니다.

1. Single Number (한 번만 등장하는 수 찾기)

문제:
정수 배열에서, 모든 숫자가 두 번씩 등장하지만 오직 하나만 한 번만 등장합니다. 그 숫자를 찾으세요.

풀이:
모든 숫자를 XOR하면, 짝수 개는 소거되어 단일 숫자만 남음.

int singleNumber(int[] nums) {
    int res = 0;
    for (int num : nums) res ^= num;
    return res;
}

2. Two Single Numbers (두 번 등장하지 않는 수 2개 찾기)

문제:
배열에 한 번만 등장하는 수가 정확히 2개, 나머지는 모두 두 번씩. 둘 다 찾아보세요.

풀이:
전체 XOR하면 x^y가 나옴. 오른쪽 첫 1비트로 그룹을 나눠 다시 XOR.

int xor = 0;
for (int num : nums) xor ^= num;
int mask = xor & -xor;
int x = 0, y = 0;
for (int num : nums) {
    if ((num & mask) == 0) x ^= num;
    else y ^= num;
}
// x와 y가 답

3. 1 비트 개수 세기 (Hamming Weight)

문제:
정수 이진수 표현에서 1의 개수를 세어라.

풀이:
Brian Kernighan 알고리즘

int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1);
        count++;
    }
    return count;
}

4. 2의 거듭제곱 판별

문제:
정수가 2의 거듭제곱인지 체크하세요 (단 하나의 1비트).

풀이:

boolean isPowerOfTwo(int n) {
    return n > 0 && (n & (n - 1)) == 0;
}

5. 부분집합 생성(Bitmask 활용)

문제:
주어진 집합의 모든 부분집합을 출력하세요.

풀이:

for (int mask = 0; mask < (1 << n); mask++) {
    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) != 0) {
            // i번째 요소 포함
        }
    }
}

6. Missing Number (0~n, 하나만 없는 수 찾기)

문제:
0~n까지의 수가 하나만 빠진 배열에서, 빠진 숫자를 찾으세요.

풀이:
배열 전체 XOR + 인덱스 XOR + n 값 ⇒ 정답

int missingNumber(int[] nums) {
    int res = 0;
    int n = nums.length;
    for (int i = 0; i < n; i++) res ^= nums[i] ^ i;
    return res ^ n;
}

7. 비트 뒤집기 (Reverse Bits)

문제:
32비트 숫자의 비트 순서를 반전하세요.

풀이:

int reverseBits(int n) {
    int res = 0;
    for (int i = 0; i < 32; i++) {
        res = (res << 1) | (n & 1);
        n >>= 1;
    }
    return res;
}

8. 두 수 스왑 (비트만으로 임시 없이 교환)

문제:
a와 b를 임시 변수 없이 스왑하세요.

풀이:

a ^= b; b ^= a; a ^= b;

9. k번째 비트 Setting/Clearing/Toggling

문제:
정수 n에서 k번째 비트를 설정/해제/토글하세요.

풀이:

// 설정
n |= (1 << k);
// 해제
n &= ~(1 << k);
// 토글
n ^= (1 << k);

요약 표

references